% Chapter X

\chapter{Background \& Related work} % Chapter title
\label{ch:backandrelwork} % For referencing the chapter elsewhere, use \autoref{ch:name} 

The main purpose of this chapter is to present all the relevant knowledge required to understand the work described in \nameref{ch:meth}.
In \nameref{sec:concepts} we discuss the basic concepts upon which the thesis has been developed with a top-down approach.
We begin by giving a quick overview of the \nameref{subsec:so} framework.
Then, we proceed by illustrating the \nameref{subsec:SI} field, focusing especially on the presentation of \nameref{subsec:SR}.

Once the context have been clarified, we state the objective of our work, the motivation behind it, its specific literature and related work in \nameref{sec:sa}.

In \nameref{sec:mat}, we conclude by giving a brief overview on the hardware and software components used in the development of the thesis. 

%----------------------------------------------------------------------------------------

\section{Concepts}
\label{sec:concepts}

\subsection{Self-organization}
\label{subsec:so}
A first, general notion that is required to fully understand the proposed methods is self-organization.
Self-organization occurs naturally in a variety of biological, chemical, and social systems.
Due to the heterogeneity and strong diversification among these categories, it is difficult to define precisely.
For our scope, we borrow a working definition from \cite{camazine2001self}:
\begin{quotation}
\emph{"Self-organization is a process in which pattern at the global level
of a system emerges solely from numerous interactions among the lower-level
components of the system.\\
Moreover, the rules specifying interactions among the system’s components are executed using only local information, without reference to the global pattern."}
\end{quotation}
A \emph{pattern} can then be seen as an organized disposition of the system components in space (or time).

Many processes in chemistry, for instance, are examples of how interactions at a microscopic level have a great influence on the final properties of a material at the macroscopic level.

One of them, \emph{Crystallization}, is the process of forming solid crystals by precipitation from a (generally) liquid solution.
It takes place when a solute (chemical compound) is mixed with a solvent, heated at high temperature.
This causes the molecules of the compound to disaggregate and start floating around.
By gradually reducing the temperature of the compound, the free solute molecules, which cannot be held anymore in the solvent, start to aggregate.
Not all the clusters of molecules become crystals, but only those who have reached a critical size (determined by the operating conditions of the process, namely temperature and pressure).
The remaining molecules then join the "surviving" aggregates, arranging themselves in a defined periodical manner that gives the crystal its characteristic structure.
It is indeed an example of \emph{self-assembling} process, analogous to the process that binds the DNA molecules to form the characteristic double helical structure.

Without restraining ourselves to chemistry, similar activities can be observed in biology as well.
Notable illustrations of the self-organizing phenomena are, indeed, morphogenesis, protein folding and homeostasis.
\emph{Morphogenesis} is a term used to identify the process through which a biological organism develops its final shape.
Many particular patterns in nature, such as pigmentation on some species of shells (Figure \ref{fig:shell}) and coat patterns in giraffes and zebras (Figure \ref{fig:zebra}) are examples of morphogenesis products.

\begin{figure}[bth]
\myfloatalign
\subfloat[Pigmentation pattern on a cone shell (Courtesy of \href{http://www.stephenwolfram.com/publications/articles/ca/83-cellular/2/text.html}{Stephan Wolfram})]
{\label{fig:shell}
\includegraphics[width=.45\linewidth]{Gfx/83cellular-f5}} \quad
\subfloat[Pigmentation patter of a zebra coat (Courtesy of \href{http://www.kk.org/thetechnium/archives/2009/08/ratcheting_up_a.php}{The Technium})]
{\label{fig:zebra}
\includegraphics[width=.45\linewidth]{Gfx/ZebraStripes}} \\
\caption[Examples of self-organizing patterns emerging from morphogenesis]{Examples of self-organizing patterns emerging from morphogenesis}\label{fig:exampleSO-2}
\end{figure}

In \cite{turing1952chemical}, Alan Turing explained the occurrence of a similar structures by means of the diffusion in the cells of chemical substances (morphogens).
By modeling this phenomenon with systems of differential equations, he discovered that a particular pattern is the result of the interaction between different types of morphogenes, some promoting and other preventing cell growth.
On the other hand, \emph{Homeostasis} is the property of system to self-regulate its internal environment to maintain a stable, relatively constant state.
This process, first studied by Bernard in the 18th Century (cf. \cite{cooper2008claude}), has been explained in the framework of dynamical systems (feedback cycles).


\graffito{"Positive feedback isn't always negative"\\--M.Resnick, Learning about Life}
Even though, at a first glance, the aforementioned processes may seem really different among them, they can all be explained through the combination of \emph{positive feedback}, that iteratively amplifies the response of the system and \emph{negative} one, which compensates by limiting it, leading the system towards stable equilibrium states.
 
From a different point of view, another relevant definition of self-organization has been given by \citep{ashby1962principles}:
\begin{quotation}
\emph{"[...] the system that starts with its parts separate (so that the behavior of each is independent of the others' states) and whose parts then act so that they change towards forming connections of some type."}
\end{quotation}

Examples of self-organizing systems in this sense, are human neural networks, whose connections and capabilities evolve across time thanks to the interconnection with similar cells.
%Even though, at first sight, the two definitions may seem unrelated among them, there are common features among them.
It should be noted the latter definition does not address the question of the usefulness of the emerging organization and that both the definitions focus on the interaction (and consequent cooperation) among the parts of the system. 
In both cases, no constraints are imposed on the basic building blocks of the system, which could be either living or inanimate entities.
Moreover, the definitions do not specify whether information is exchanged among the agents during their interaction and how such knowledge is used in the process.

The research in \nameref{subsec:SI}, on the other hand, is focused on the study of self-organizing behaviors  of a precise typology of entity: \emph{agents} (i.e. entities capable of observing and modifying their environment by means of, respectively, sensors and actuators).

%----------------------------------------------------------------------------------------

\subsection{Swarm Intelligence}
\label{subsec:SI}

What is, then, an intelligent swarm? We can find a good answer in \cite{beni2005swarm}:
\begin{quotation}
\emph{"[...] a group of “machines” capable of forming “ordered” material patterns “unpredictably”."}
\end{quotation}

This definition allows us to immediately clarify the most important aspects concerning this discipline.
First of all, the fact of dealing with systems composed by multiple individuals which are able to organize themselves autonomously.
The intelligence of the swarm is expressed in terms of computational equivalence.
Its unpredictability arises from the fact that it is as powerful as any other universal computational model.

Moreover, the notion of machine (as \emph{"[...] an entity capable of processing matter/energy"}, from \cite{beni2005swarm}) does not define the nature of the entity itself which could be either a living creature (\emph{Natural} \acl{SI}) or a human artifact (\emph{Artificial} \acl{SI}). 

\emph{Natural} \acl{SI} deals with the study of the collective behaviors emerging from the interactions of biological organisms (generally animals or insects).

The most fascinating examples in this category, under a visual point of view, are surely the flocking (schooling) behavior that can be observed in groups of birds (fish).
While displaying a similar behavior (Figures \ref{fig:flock}, \ref{fig:school}), the group of animals moves as if it were a single, fluid entity.
Furthermore, even though rapid changes of direction are triggered as a reaction to events in the environment (e.g. presence of a predator/obstacle) accidental collisions among the individuals are rare.
Surprisingly, a limited set of rules (three, to be precise, cf. \cite{reynolds1987flocks}) describing the inter-agent interactions and local sensing capability are sufficient to achieve this complex global behavior.

Insects are an interesting example of how organization can be achie\-ved when the number of individuals scales up from tens to thousands of units in the group.

For instance, ants of the \emph{Pheidole} genus are divided two distinct categories of individuals: minors 
and majors. 
Insects from the former category carry out the majority of the tasks required in the colony (grooming, brood care, foraging) while those in the latter focus on nest defense and seed milling.
As shown in \cite{wilson1984relation}, when the ratio minors:majors drops below a certain threshold, the repartition of the activities among the agents is modified in a way that majors compensate for the lack of minors by performing their tasks.
If the ratio is increased again, the ants recover the original task allocation.
An explanation of this adaptive unsupervised division of labor, has been given several years later with the response-threshold model (\cite{theraulaz1998response}), based only on features of each agent.  

Bees, on the other hand, show us how the global structure of their hive can emerge from the independent, but self-organized work of a large number of individuals (Figure \ref{fig:bees}).
An honey bee colony presents in fact a characteristic pattern, made by three concentric zones containing respectively brood, pollen and honey (from the center to the exterior area).
A first hypothesis that has been formulated to describe this phenomenon was that bees possessed some innate knowledge about how to arrange cells (e.g.blueprint or pattern).
What \cite{camazine1991self} has shown, is that brood is initially deposed in a compact way by the queen, while pollen and honey are dispersed randomly in the structure or in cells where the same substance is already present.
The structure then emerges from a simple nourishment\footnote{Pollen and honey.} displacement behavior performed by all the agents, based on brood quantity in the neighborhood, along with the different rates at which new substances are brought in the colony.

Evidence of the emergence of a collective intelligence through simple interactions in a large group of individuals have been observed in humans as well.
In \cite{krause2010swarm} we find the application of this principle to different real situations such as the guess of the exact quantity of marbles in a jar, the management of a football team, the design of a new product. 
The main benefit of a similar cooperation in humans is the collective information processing to
provide a new cognitive solution to a problem.

\begin{figure}[!h]
\myfloatalign
\subfloat[Flock of auklets (seabirds). (Courtesy of D. Dibenski)]
{\label{fig:flock}
\includegraphics[width=.45\linewidth]{Gfx/flocking-birds}} \quad
\subfloat[School of fishes swimming together in a spherical formation.]
{\label{fig:school}
\includegraphics[width=.45\linewidth]{Gfx/schooling-fish}} \\
\subfloat[Major and minor ants of the \emph{Pheidole} genus taking care of the colony brood. (Courtesy of \href{http://www.alexanderwild.com/}{Alexander Wild})]
{\label{fig:ants}
\includegraphics[width=.45\linewidth]{Gfx/antsMinorMajor}} \quad
\subfloat[Bees deposing honey in their colony. (Courtesy of \href{https://secure.flickr.com/photos/27330306@N08}{Kamillo Kluth})]
{\label{fig:bees}
\includegraphics[width=.45\linewidth]{Gfx/bees}} \\
\subfloat[Exemplification of the "Wisdom of crowds" concept.]
{\includegraphics[width=.45\linewidth]{Gfx/crowd}}
\caption[Examples of \acl{SI}]{Examples of \acl{SI}}\label{fig:example}
\end{figure}


Why are these behaviors widely observed in nature? Why there is an interest in their study from an engineering standpoint?
An answer can be found in the characteristics that these systems possess.

First of all, they are completely \emph{distributed}, in the sense that there are no leading individuals in the group that impose a certain behavior, neither locally nor globally.
Furthermore, all the agents are relatively \emph{homogeneous} (i.e., they present only limited variability in terms of morphology or capabilities) with only \emph{local sensing} capabilities (that is, they could only have insights on what is happening in their surroundings, but not at a global level).
The combination of this features implies that no individual is essential to the survival of the group, thus ensuring the ability to cope with the loss of individuals (due to death or temporary/permanent inability), hence the \emph{robustness} of the system.
Moreover, through simple behavioral rules concerning the interaction with other agents and basic information transfer, both direct or indirect (e.g. stigmergy), a collective, intelligent organization emerges.
This locality allows the system to be \emph{resilient} with respect to both the fluctuations in the environment and in the swarm.
As we may notice, all the aforementioned features brings a set of advantageous properties to the system.

The research in \acl{SI} is mainly twofold.
On one hand, the aim is to understand the mechanisms underlying such kind of systems and provide a model which is able to explain the emergence of a collective behavior (\emph{Scientific \acl{SI}}).
Since \acl{SI} is a bio-inspired discipline, the largest part of this research is conducted by life scientist.
On the other hand, the focus is how to apply the discovered knowledge to problems having a practical relevance (\emph{Engineering \acl{SI}}).
In this case, researchers in computer science, mostly in artificial intelligence and robotics, are using the knowledge gathered in other fields to create algorithms able to solve optimization problems, to perform realistic simulations of thousands of agents or develop efficient robotic systems.

%----------------------------------------------------------------------------------------

\subsection{Swarm Robotics}
\label{subsec:SR}
In the first years of 1990, while life scientists \citep{camazine1991self} were observing and modeling the behavior of social insects, the first examples of multi-agent systems were being developed by computer scientists (\cite{singh1991towards}).

These artificial systems are composed by a group of autonomous entities interacting among them and with an environment, which can be either physical (e.g robots in a real environment) or virtual (software agents, for example).
The nature (physical/virtual, human/artificial) and the complexity of the agents (active/passive, cognitive/reflexive) could be highly variable, yielding to heterogeneous sets of agents.
Over the years, similar systems have been mainly used to perform distributed problem-solving (\cite{colorni1991distributed}) or multi-agent simulation of real world processes (\cite{benenson1998multi}).

In the years 2000, the biological and artificial research paths have joined in the \acl{SR} field.
%As we saw in \nameref{sec:SI}, swarm systems are really diffuse in nature and possess several interesting properties.

A more precise definition can be found in \cite{csahin2005swarm}:
\begin{quotation}
\emph{"Swarm robotics is the study of how large number of relatively
simple physically embodied agents can be designed such that a desired collective
behavior emerges from the local interactions among agents and between the agents
and the environment."}
\end{quotation}

A physical embodied agent is an entity whose behavior is affected by its morphological features and the environment it is situated in \citep{pfeifer2007self}.
In order for the agent to be embodied, it must be able to transfer and process matter, energy (through its actuators) and information (by means of its sensors and its internal architecture), hence it must be, according to \cite{beni2005swarm}, a robot.

As a consequence, we can observe from the definition that \acl{SR} is a branch of collective robotics where a global behavior is achieved through the self-organization of the individuals.
The autonomous agents are relatively simple in the sense that they are equipped with a minimal set of sensors and actuators, that prevents each agent from having a \emph{global knowledge} of the system and the environment.

It is important to clarify that, while the definition deals with a large number of robots (from hundred to thousands of robots), the empirical experiments in \acl{SR} are performed with group of at most 30 to 50 robots.
This discrepancy is mainly due to practical and economical reasons.
In fact, even though the technological evolution allowed to reduce the costs of the microelectronic components that constitute a robot, a single assembled agent still remains costly (from several hundred to several thousands euros).
Furthermore, most of the robots used in the experiments are battery-powered, which constrains the autonomy of the robots to those of their power supply.

Despite of these limitations, why there is still an interest in \acl{SR}?
The answer to this question can be found by analyzing how self-organization can solve some common issues in collective robotic.
For instance, the robot coordination in many application of collective robotics is achieved through a shared, centralized communication medium, which is accessed concurrently by all the agents.
A similar solution has some major drawbacks: if the medium is unavailable, the system cannot operate correctly.
Moreover, the quality of the communication decays as the number of robots in the system increases, due to the concurrency.
Conversely, if the coordination is achieved through local interactions of the robots, the \emph{robustness} of the system with respect to faults and disturbances can be achieved.
The points of failure will then become distributed among the agents, lowering their influence on the overall performance of the system. 
Also, if the agents are homogeneous and relatively simple, the swarm becomes even more dependable by means of \emph{redundancy}.
In addition, the lack of a central communication mechanism favors the \emph{scalability} of the system with respect to changes in the number of individuals.
Another advantage of self-organization is that robots could operate autonomously, hence performing \emph{parallel} activities which are distributed in space and in time, improving the global efficiency of the system.

It is important to stress the fact that the aforementioned properties are not guaranteed as a consequence of self-organization.

\subsubsection{Development methodology}
\label{subsubsec:devmeth}
\begin{figure}[!h]
\begin{center}
\begin{tikzpicture}[node distance=1.5cm,auto,>=latex']
    \node [draw, dashed, minimum size=2em] (a) {Requirement specification};
    \node [draw, minimum size=2em] (b) [below of=a] {Design};
    \node [draw, minimum size=2em] (c) [below of=b] {Implementation};
    \node [draw, minimum size=2em] (d) [below of=c] {Test and Analysis};
    \node [draw, minimum size=2em] (e) [below of=d] {Validation};
    \node [draw, dashed, minimum size=2em] (f) [below of=e] {Operation and maintenance};
	\node [minimum size=2em,node distance=4cm,text width=3cm] (g) [right of=b] {Behavior-based 
	Automatic};
	\node [minimum size=2em,node distance=4cm,text width=3.3cm] (h) [right of=d] {Microscopic level 
	Macroscopic level};
	\node [minimum size=2em,node distance=4cm,text width=3.3cm] (i) [right of=e] {Simulation 
	Real robots};    
    \path[->] (a) edge  (b);
    \path[->] (b) edge  (c);
    \path[->] (c) edge  (d);
    \path[->] (d) edge  (e);
    \draw[->] (e) edge  (f) ;
    \draw[->] (b) edge  (g) ;
    \draw[->] (d) edge  (h) ;
    \draw[->] (e) edge  (i) ;
\end{tikzpicture}
\end{center}
\caption[Overview of the typical development process in \acl{SR}]{Overview of the typical development process in \acl{SR}.

Backward feedback loops are omitted for clarity. 

The elements having a dashed border are not generally performed in the context of \acl{SR}.}\label{fig:swarmDevelopment}
\end{figure}


Indeed, the main research question in \ac{SR} is how to develop design methodologies at the individual level that will cause the emergence of a collective behavior exhibiting the aforementioned properties.
 
%This can be done by taking advantage of the features of the environment and the characteristics of the task that the swarm has to perform.

Figure \ref{fig:swarmDevelopment} depicts the typical development process in \acl{SR}.
The systematic application of scientific and technical knowledge in a structured way in the development process is generally referred as Swarm Engineering. 

Concerning the \emph{design} step, there are two common approaches, \emph{behavior-based} and \emph{automatic}.

The \emph{behavior-based} one is a process that consists in developing (often by hand, in a trial-and-error fashion) a specification of the agents behavior which can be easily implemented.
\graffito{The interested reader could find all the details and relevant articles describing their application in \protect\cite{brambilla2013swarm}}
According to \cite{brambilla2013swarm} the most used methods in this category are the \emph{finite state machine} and \emph{virtual physics} one.
The \emph{finite state machine} one is based on the definition of a set of relevant states for the robot and the corresponding transitions, based on the inputs from the sensors and on the robot current state.
\emph{Virtual physics} \citep{spears2004distributed} treats each agent as a virtual particle subject to virtual forces.
Those forces are the result of the interaction of the robot with a virtual potential field, that can be perceived through its sensors.

As for \emph{automatic} methods, the idea is to apply \acl{AI} techniques to the design process of the robot, without relying on human-based development.
The most frequently used techniques are \ac{RL} and \ac{ER}.

With \acl{RL} \citep{sutton1998reinforcement} the agent learns a desired individual behavior by means of iterated interactions with the environment, receiving a feedback on its actions.
The polarity (positive or negative) of the feedback, determines whether the agent should retain or forget a certain component of the behavior.

In \acl{ER}, evolutionary computation techniques \citep{goldberg1988genetic} are applied to the swarm of robots.
The individual behavior of the robots (identical for all the agents) is the basic component that is evolved through different iterations of the method.
At the beginning, this behavior is generated randomly and the collective behavior produced by the simultaneous execution of it on all the robots is evaluated by means of a fitness function.
At each iteration, the individual behaviors are modified by means of selection, recombination and mutation operations.
The process is stopped once the desired collective behavior has been achieved.
 
After the design phase have been completed, the emerging behavior must be thoroughly analyzed in order to assess whether the desired properties hold or not, before actually validating it with tests on the real robots.
The \emph{analysis} is performed mainly by means of \emph{simulations} and \emph{mathematical models}.

\emph{Simulations} offer a swarm representation which is as close as possible to the reality, by modeling each robot component at a microscopic level. 
Unfortunately, this accuracy comes at the price of computational complexity, which dramatically increases as the number of agents becomes larger, making technically unfeasible the simulation of numerous swarms.

On the other hand, \emph{mathematical models} based on the theory of dynamical systems or on the control and stability theory can be used to describe the system at a macroscopic level. 
They can be studied regardless of the group size, but their extent is often restricted to simplified representations of the systems to study, limiting their practical utility.

The final step of this engineering process is the execution of the individual behavior by a swarm of real agents.
Surprisingly, as \cite{brambilla2013swarm} shows, the validation on real robots is performed on less than half of the papers that the authors have reviewed.

The validation through simulation of the results presents some clear advantages: it prevents damages to the robot in case of a behavior fault, it can be easily parallelized thus being executed faster, it does not require the actual deployment and maintenance of the robots.
However, the lack of experiment in the real environment of the robots does not give any guarantees on the feasibility of the methods and on the realism of the underlying assumptions.

\subsubsection{Applications of \acl{SR}}

\begin{table}
\myfloatalign
\begin{tabularx}{\textwidth}{p{5.5cm}|p{5.5cm}} \toprule
\tableheadline{Scientific} & \tableheadline{Engineering} \\ \midrule \midrule
 \begin{itemize}
 \item Aggregation
 \item Pattern formation
 \item Self-assembly
 \item Coordinated motion
\end{itemize}  &  \begin{itemize}
 \item Self-assembled motion
 \item Area coverage
 \item Collective indoor exploration
 \item Collective transport
 \item Consensus achievement
 \item Task allocation
 \item Fault detection
 \item Group size regulation
\end{itemize} \\ \midrule
\bottomrule
\end{tabularx}
\caption[Summary of the applications of \acl{SR}]{Summary of the applications of \acl{SR}. The task typologies are those presented in \cite{brambilla2013swarm}.}  
\label{tab:application}
\end{table}

As we discussed in \nameref{subsec:SR}, the affordability and the maintenance issues of a swarm of real robots are the problems that hinder the creation of swarm-based solutions that can operate in everyday life.

Nevertheless, the research in \acl{SR} has provided valuable insights on the functioning of self-organized biological systems and proofs-of-concept regarding how agent cooperation can successfully tackle complex problems. 
Hence, according to the taxonomy defined in \cite{Dorigo:2007}, these results can be classified as \emph{Artificial \acl{SI}} with both \emph{Scientific} and \emph{Engineering} purposes.

Under a \emph{scientific} point of view, the most fruitful applications are related to collective behaviors that cause the emergence of patterns with a precise connotation in space.
For instance, \cite{garnier2005aggregation} have successfully designed a robot controller that causes the formation of group of agents in defined regions of the space (i.e. their \emph{aggregation}), replicating the behavior of cockroaches.
In addition, the \emph{chaining} behavior of ants have been modeled and implemented on artificial agents, both with \citep{mondada2005superlinear} and without \citep{nouyan2008path} physical connection among the agents.
Also, the \emph{flocking} behavior, the most known example of \emph{coordinated motion}, depicted in figures \ref{fig:flock} and \ref{fig:school}, has been achieved with a group of robots \citep{balch2000social}.

Studies in \acl{SR} has not only proven to be useful in explaining the underlying mechanisms that trigger the emergence of \acl{SI} in animals and insects, but also in developing solutions to problems having a practical relevance (i.e. from a \emph{engineering} standpoint).

Here, the most interesting results have been obtained while dealing with \emph{environment exploration}, \emph{object transport}, \emph{swarm awareness} and \emph{decision making} problems.

Within the \emph{exploration} framework, solutions have been found by deploying robots in a way that they maximize the \emph{area coverage} of the given environment, sometimes by having a connectivity constraint among the agents \citep{howard2002mobile} or by using an heterogeneous swarm, in order to take advantage of the different characteristics of the individuals \citep{ducatelle2011self}.

\emph{Collective object transport} has been successfully tackled by a group of robots, simply by relying on the force, position and orientation sensing of each agent \citep{donald1997information}.

Some methods have also been developed to make the swarm \emph{aware} of its current state, for example, by being able to \emph{detect} the presence of \emph{faulty robots} \citep{christensen2009fireflies} or estimate and regulate its group size \citep{brambilla2009reliable}.

Moreover, the problem of having the swarm reach a \emph{consensus} concerning a choice (e.g. moving direction, aggregation point) that will affect the performance of the whole group, have been solved using both direct \citep{gutierrez2010collective} and indirect communication \citep{garnier2005aggregation}.

Last but not least, the problem of \emph{allocating} robots to different tasks (foraging against resting) in order to maximize the throughput of the system have been successfully addressed with an individual decision mechanism \citep{krieger2000call}.
 
We are aware that the overview we presented may be incomplete, but its main purpose is to illustrate the most prominent results obtained in \acl{SR}.


%----------------------------------------------------------------------------------------

\section{Spatial allocation}
\label{sec:sa}

In this thesis we investigate the problem of allocating embodied agents to physical tasks distributed in space.
A brief example might clarify this description. 

Consider a search and rescue scenario: some people are dispersed in an hazardous environment (e.g. a building on fire) and they need help in the shortest possible time.
The nature of the environment generally impedes a global exchange of information among the rescuers, making a centralized coordination of the process unfeasible.
Moreover, the information concerning the topology of the environment and the number of people in distress may be unavailable or unreliable.
If we consider that robots are, in general, faster, stronger, more resistant and more accurate than human, we could foresee the application of a swarm of robots to operate in the aforementioned dangerous environment.
In any case, the only operable solution would be to let the rescue agents self-coordinate themselves during the process.
The optimal allocation, in a similar scenario, would be the one allowing to rescue all the people in the shortest possible time.

Indeed, the fundamental aspects that characterize the performance of the method are the \emph{uniformity} of the distribution of agents across the requests in the environment and the \emph{time} needed to discover and allocate to the task.

The collective behavior that the robots should achieve is in between the \emph{task allocation} and the \emph{foraging} activity (cf. Figure \ref{fig:map}). 
In fact, in the context of \acl{SR}, the \emph{task allocation} problem is usually related to the choice among different alternatives, which are known a priori, concerning the role of the agents in the swarm \citep{krieger2000call,agassounon2002efficiency,pini2009interference}.

On the other hand, \emph{foraging} is the process of collectively searching for resources scattered in the environment, harvesting them and depositing them at predefined collection points.
This activity can be decomposed into four phases.
First, the robots have to employ a search strategy (e.g.~uninformed random walk) to \emph{localize} the resource in space.
Once the object has been found, the agent have to physically \emph{collect} it.
Then, it must apply a \emph{navigation} strategy to head back to the collection point.
Lastly, the robot \emph{deposit} the gathered object and restart the process.
A detailed taxonomy of the process can be found in \cite{winfield2009towards}.

Moreover, according the taxonomy defined in \cite{gerkey2004formal} our problem could be classified as ST-SR-IA (Single Task, Single Robot, Instantaneous Assignment).
As a matter of fact, we analyze a problem in which homogeneous agents (i.e. no difference among them) should
\emph{localize} homogeneous tasks (that is, any robot could potentially allocate itself to any activity) in space and then \emph{decide} whether their allocation to the task is required or not.
  
\subsection{Related work}
\label{subsec:relwrk}

\begin{figure}[!htb]
\begin{tikzpicture}
  \path[mindmap,concept color=black,text=white]
    node[concept] {Spatial Allocation}
    child[grow=-180,concept color=green!50!black] {
      node[concept] {Multi-robot task allocation}
      [clockwise from=-135]
      child { node[concept] {Decentra\-lized}      		  
      		  child[grow=145]{node[concept] {Market-based} }
       		  child[grow=190]{node[concept] {Response-threshold} }
       		  child[grow=235]{ node[concept] {DCSP}}
       		 }
      child { node[concept] {Centra\-lized}      		  
      		  child[grow=145]{node[concept] {OAP} }
       		 }
    }
    child[grow=-90,concept color=blue] {
      node[concept] {Collective foraging}
    };
\end{tikzpicture} 
\caption[Map of the relevant concepts related to Spatial Allocation]{Map of the relevant concepts related to Spatial Allocation}\label{fig:map}
\end{figure}

In our vision of the problem, the only common subtasks with the \emph{foraging} activity are the \emph{localization} and the \emph{collection} one.
The \emph{navigation} and \emph{deposit} operations are outside of the scope of our methods.
As for the \emph{localization} problem, several techniques of \emph{collective exploration} such as \emph{area coverage} \citep{spears2004distributed} or \emph{chain formation} \citep{nouyan2008path} could be potentially employed.
Instead, we choose to implement a simplifed and unbiased exploration technique: \emph{random walk}.
In addition, the \emph{collection} operation will be abstracted by means of a specific device (i.e. \emph{TAM}).
 
For these reason, we choose to focus our related literature analysis on the \emph{task allocation} instead of the \emph{foraging} activity.
Here, we can distinguish two different approaches: \emph{centralized} and \emph{decentralized}.

\emph{Centralized} approaches are based on the modeling of the allocation activity as an optimization problem, the \ac{OAP} \citep{gerkey2004formal}.

In the classical formulation of the problem \citep{gale1960theory}, there are $m$ agents that have to be assigned to $n$ jobs.
Each agent $i$ is characterized by a utility estimate value $U_{ij}$ that predicts his performance on task $j$.
The optimal solution of the problem consists in the allocation of agents to jobs that maximizes the system performance (utility).
By gathering all the information concerning the agents in a single entity, which can be either a robot in the group or an external computation device, it is possible to obtain a solution using a combinatorial optimization algorithm (e.g. the Hungarian method \cite{kuhn1955hungarian}).

A similar approach requires complex communication capabilities and a global knowledge of the characteristics of the agents in order to be effective, requirements that are generally not met on real \acl{SR} applications.

Moreover, in case of malfunctions or unavailability of the single allocator entity the whole system ceases to function. Also, the centralized collection of information introduces a bottleneck in the system.
We can conclude that this approach lacks of robustness and scalability, thus being unsuitable for swarm implementations.

Decentralized approaches can be classified according to the type of coordination they employ.
On one hand, we have \emph{intentional coordination} among the agents, as in \emph{market-based} approaches,
for whose detailed survey of can be found in \cite{dias2006market}.
The underlying principle is similar to the \ac{OAP} one.

Each agent possesses, in fact, an individual utility function that quantifies its preferences for the allocation to a certain task.
In addition, the agent can estimate the cost (e.g. the distance, the energy consumption) related to the task it is seeking allocation for.

Whenever more than one agent is interested in a certain task, an auction process is started.
On basis of the information it possess, it makes a certain bid for the task.
The agent with the highest bid wins the auction process and gets the task.

Examples of approaches in this category are \cite{lin2005combinatorial,guerrero2003multi}.

An advantage of this method is that the auction process does not necessarily require global or perfect information.
Unfortunately, the bidding process is particularly demanding in terms of communication resources, since it requires an iterated exchange of messages by all the parties involved in the transaction and does not scale well as the number of robots increases.

On the other hand, \emph{coordination emerges} from simple interactions among the agents, as in \emph{response-threshold based} approaches, which draw inspiration from nature.

The response-threshold model, developed by \cite{theraulaz1998response}, assumes that each task in the environment has an associated stimulus.
Each agent has a different response threshold for the available tasks and its probability to engage in the activity is a function of the threshold and the value of the stimulus.
The stronger the stimulus, the higher the likelihood that an agent will allocate itself to a certain task.
The threshold can be either fixed (as in the original model) or adaptive (in a \acl{RL} fashion).
In the latter case, the decrease of the threshold value for a certain activity can make an individual more sensible to the corresponding stimulus, resulting in more frequent allocation.
Conversely, an agent will be more reticent to allocate to a certain task when the corresponding threshold is raised.
Since the allocation decision is performed without direct communication among the agents, the approach scales well as the number of agents increases.
Moreover, it is robust with respect to faults on the robots and flexible with respect to variations in the demand.
The main drawback of this approach is the difficulty to predict the emergent behavior of the system, making the design of a system for a specific purpose problematic.
A comparative analysis among the two mentioned approaches has been done by \cite{kalra2006comparative}, showing a better performance of the response-threshold approach with respect to the market-based one when the information is inaccurate.

The multi-robot task allocation problem can also be seen as an instance of the Constraint Satisfaction Problem.
The problem consist in finding an assignment of values to a set of variables $V$ from the corresponding domains set $D$ that respect the set of constraints $C$.
If we consider $V$ as the set of tasks, $D$ as the set of robots and we introduce the constraint that each robot must be assigned to exactly one task we obtain the single robot, single task allocation problem.
In \cite{shen2002towards}, this problem is approached in a distributed fashion (\ac{DCSP}).
The proposed solution however, is particularly demanding in terms of task modeling and information exchange among robots, thus difficult to apply on large groups of robots.  
Up to now, to the best of our knowledge, there are no studies that explicitly concentrate
on the allocation of robots to physically situated activity with a self-organizing approach.

Despite having a completely different approach, the work from \cite{hsieh2008biologically} addresses a problem closely resembling ours.
Their problem involves $N$ agents to be distributed among $M$ sites in an environment whose topology can be expressed as a graph $\mathcal{G(V,E)}$, in terms of sites ($\mathcal{V}$) and one-way connections among them ($\mathcal{E}$).
The state of the system is represented by the relative number of agents at each site $i$ ($x_i(t)$).
The authors propose two strategies for redistribution: \emph{baseline} and \emph{quorum-based}.
In the first one, the distribution of the agents occurs by means of transition probabilities per unit of time ($k_{ij}$) between nodes, defined on every edge in $\mathcal{E}$.
In the second one, each site has an associated quorum value $q_i$.
Whenever the current occupation $x_i(t)$ is above the quorum then one of the outgoing transitions rates from that node is multiplied of a coefficient $\alpha$ until the occupation descends again below the quorum value.
In both cases, the entries of $\mathbf{K}$ (i.e. $k_{ij} \forall i,j$) are determined using Metropolis optimization \citep{landau2009guide}.

Even though the model allows to obtain promising results, successfully achieving the redistribution of a swarm of 20000 robots, there are some strong assumptions that differentiate this approach from ours.
First of all, the agents do possess a global knowledge of the topology of the environment ($\mathcal{G(V,E)}$) and thus are capable of localizing themselves and navigating easily from one site to another.
Moreover, the robots are supposed able to estimate the current occupation $x_i(t)$ of the site they are in.
Also, the results are obtained only with simulations where real-world non-linear effects on the sensors and actuators along with realistic deployment dynamics for the robot have not been modeled.
Although the stochastic transition polices are defined at an agent-level and do not require any wireless communication, the actual values of the transition probabilities are computed off-line and then distributed to all the agents, making the proposed solution de facto centralized.

In contrast to \cite{hsieh2008biologically}, our purpose is to distribute uniformly agents across spatially distributed tasks, in real-time, without global information concerning the topology of the environment or the transition rates. 

\section{Materials}
\label{sec:mat}

Since we are going to develop a method in the context of \acl{SR}, we must clarify two fundamental aspects: the \emph{characteristics} of the embodied agents and the \emph{development} methodology we are going to adopt.

Our embodied agents are mobile robots, the \emph{e-pucks}, presented in detail in the \nameref{subsec:epuck} section.

A novel point in our approach is that tasks are abstracted but embodied as well, by means of a specifically designed device, the \emph{TAM}, whose specifications will be discussed in \nameref{subsec:TAM}.

As for the \emph{development} methodology, we are going to adopt a behavior based approach (explained in \nameref{ch:meth}) with a microscopic-level simulation-based analysis.
All the relevant information concerning the multi-robot simulator can be found in \nameref{subsec:ARGoS}.

\subsection{E-puck}
\label{subsec:epuck}

\begin{figure}[H]
\includegraphics[width=\linewidth,keepaspectratio]{Gfx/e-puckAnnotated}
\caption[Annotated picture of the e-puck robot]{Annotated picture of the e-puck robot. (Courtesy of \href{http://www.roadnarrows-store.com/}{RoadNarrows})}
\label{fig:epuck}
\end{figure}

\graffito{Only the relevant aspects for the thesis have been discussed here.
For more details concerning the robot, visit \url{http://www.e-puck.org}}
The \emph{e-puck} (Figure \ref{fig:epuck}) is an open-source educational desktop mobile robot \citep{mondada2009puck}.
It has been developed at the EPFL (Ecole Politechnique Federale de Lausanne), in order to provide a common robot platform to be used in a broad range of university courses.
The \emph{educational} purpose of the robot has influenced its design process.

The compact and modular shape of the robot is thought to be \emph{robust} with respect to the student use but easy to repair at the same time.
Moreover, its size has been conceived make the robot usable also in relatively small environment, like a desk.

In addition, the robot is equipped with several different sensors and actuators  as well as with an expansion board, making the robot flexible and usable in a wide range of contexts (from signal processing to automatic control, for example).

In order to favor the diffusion of knowledge and the improvement of the robot, the designers have given open access to its hardware specifications and distributed the related software with an open source license.

The publication of all the information concerning the robot has made the development of extension boards for the \emph{e-puck} possible.
Among the different available extensions, we focus only on those relevant for the development of our methods: the \emph{omni-directional camera} and the \emph{\ac{RAB}} board.
%\graffito{For more details concerning the omnidirectional camera, visit \url{http://www.e-puck.org/index.php?option=com_content&view=article&id=26&Itemid=21}}

The \emph{omni-directional camera} is build by encapsulating the standard \emph{e-puck} camera in a glass cylinder, with an hyperbolic mirror on the opposite edge.
By pointing the camera towards the mirror it is possible to obtain a 360 degrees viewing range around the robot.
The board, containing the CMOS camera, a FIFO buffer and an additional microcontroller, is mounted on top of the robot and connected to it by means of a card-edge connector leaving the possibility to connect other extensions to the \emph{e-puck}. 

The \emph{\acl{RAB}} board is an extension developed to provide local communication capabilities to the robot \citep{gutierrez2008open}.
By means of 12 \acs{IR} emission/reception modules, nearly uniformly distributed on the perimeter of the board, the \emph{e-puck} becomes capable of broadcasting up to 16 bit of information to the nearby robots.
The board takes its name from the fact that, given the power of the received signal and the placement of the sensors/actuators, the embedded microcontroller on the board is able to compute the range (distance) and bearing (angle with respect to the receiver) of the sender robot.
 
Figure \ref{fig:TAM} shows an \emph{e-puck} with both the aforementioned extensions installed.

We decided to choose the \emph{e-puck} as the robotic platform for the development of our methods since it is a simple yet powerful device which best represent the notion of swarm agent.

If we look at the specifications (Table \ref{tab:epuckspec}), we may notice the \emph{limited sensing capability}, especially with respect to the sensors we are going to use in our method: the \emph{proximity sensors} and the \emph{camera}. 

%Furthermore, the robot is only endowed with \emph{local communication} capability (Bluetooth).
%Discuss later

The affordability and reduced size (with respect to similar devices) makes also  the creation of a large swarm of robots feasible.

\graffito{Phototaxis is a kind of taxis, or locomotory movement, that occurs when a whole organism moves in response to the stimulus of light.}
Although the \emph{e-puck} possesses a wide set of sensors and actuators, we are only going to use those required to perform displacements (\emph{wheels}), obstacle avoidance (\emph{proximity sensors}) and odometry (\emph{encoders}), plus the functionalities offered by the extension boards to perform phototaxis (\emph{omni-directional camera}) and local communication (\emph{range and bearing system}).

\begin{table}[H]
\begin{scriptsize}
\begin{tabularx}{\textwidth}{p{2cm}|p{5cm}} \toprule
\tableheadline{Features} & \tableheadline{Technical information} \\ \midrule \midrule
\tableheadline{Size and weight} &	70 mm diameter, 55 mm height, 150 g \\ \midrule
%Battery autonomy & 5Wh LiION rechargeable and removable battery providing about 3 hours autonomy \\ \midrule
\tableheadline{Processor (Robot)} & dsPIC 30F6014A @ 60 MHz (~15 MIPS) 16 bit microcontroller with DSP core \\ \midrule
\tableheadline{Controller (Omnidirectional camera)} & dsPIC33FJ256 GP506 16 bit microcontroller with (Averlogic AL440B-24-PBF) (FIFO) frame buffer \\ \midrule
\tableheadline{Controller (RAB board)} & dsPIC 33FJ256 16 bit microcontroller \\ \midrule
%Memory & RAM: 8 KB; FLASH: 144 KB \\ \midrule
\tableheadline{Motors} & 2 stepper motors with a 50:1 reduction gear \\ \midrule
\tableheadline{Encoders} & One per wheel, pulses resolution: 0.13 mm \\ \midrule
%Speed & Max: 15 cm/s \\ \midrule
%Mechanical structure & Transparent plastic body supporting PCBs, battery and motors \\ \midrule
\tableheadline{Proximity sensors} & 8 \acs{IR} sensors uniformly placed below the ring\\ \midrule
\tableheadline{Camera} & 2 \acs{CMOS} VGA color camera, resolution: 480x640 pixels (4 fps at 40x40) (Front and omni-directional) \\ \midrule
\tableheadline{RAB emission/reception module} & Infrared
emitting diode with infrared modulated receiver and infrared photodiode.
 \\ \midrule
\tableheadline{Microphones} & 3 omni-directional microphones for sound localization \\ \midrule
\tableheadline{Accelerometer} & 3D accelerometer along the X, Y and Z axis \\ \midrule
\tableheadline{LEDs} & 8 red LEDs (ring), green LEDs (body), one strong red LED (front) \\ \midrule
\tableheadline{Speaker} & On-board speaker (WAV and tone sound playback) \\ \midrule
%Switch & 16 position rotating switch on the top of the robot \\ \midrule
\tableheadline{Connectivity} & Serial port (RS232), Bluetooth, \ac{IR} Remote control \\ \midrule
\tableheadline{Programming languages} & C (General purpose), ASM (DSP)  \\ \midrule
\bottomrule
\end{tabularx}
\end{scriptsize}\caption[Overview of the technical specifications of the \emph{e-puck} robot]{Overview of the technical specifications of the \emph{e-puck} robot}  
\label{tab:epuckspec}
\end{table}


\subsection{IRIDIA \acl{TAM}}
\label{subsec:TAM}

\begin{figure}[H]
\centering
\includegraphics[width=0.7\linewidth,keepaspectratio]{Gfx/tam_v4_simple_epuck}
\caption[Picture of the \ac{TAM} with an \emph{e-puck} with the range and bearing board and the omni-directional camera extension]{Picture of the \ac{TAM} with an \emph{e-puck} with range and bearing board and the omni-directional camera extension (Courtesy of \href{http://iridia.ulb.ac.be/~abrutschy/index.php}{Arne Brutschy})}
\label{fig:TAM}
\end{figure}

The IRIDIA \acs{TAM} is a device for task abstraction specifically designed for the \emph{e-puck} robot \citep{Brutschy:TechRep:2010}.
Due to its physical structure, the robot cannot be extended by means of a manipulation device (e.g a gripper) thus limiting the number of activities that the robot could actually undertake.

The \acs{TAM} comes from the idea that the tasks that are beyond the capabilities of the robot could be instead simulated.  
It has been designed as an U-shaped booth (Figure \ref{fig:TAM}) that could welcome a robot, whose presence can be detected by means of the \emph{light barrier}.
The task abstraction occurs through the interaction between the device and the \emph{e-puck}.
In fact, the \acs{TAM} is a programmable device which can display its internal state through the colors of the \emph{RGB LEDs}.

It is a duty of the researcher to find a suitable representation of the task, given the functionalities of the aforementioned device.
An example of a successful application of this device is \cite{pini2011task}, where a group of \emph{TAM} is used as a cache site to simulate the deposit and pick up of objects.

In the context of our work, we take advantage of the fact that a \emph{TAM} could be seen as a physical representation of an activity, thus having a precise collocation in space.
Indeed, \emph{TAMs} will model the spatially distributed tasks that will require the allocation of a robot.

\begin{table}[H]
\begin{scriptsize}
\begin{tabularx}{\textwidth}{p{2.5cm}|p{6.5cm}} \toprule
\tableheadline{Features} & \tableheadline{Technical information} \\ \midrule \midrule
\tableheadline{Sizes} & 120 mm x 120 mm x 108.3 mm (height x width x depth) \\ \midrule
\tableheadline{Processor} &  Atmel ATmega168 @ 20 MHz (~20 MIPS) 8-bit microcontroller \\ \midrule
\tableheadline{Battery} & 5Wh LiION rechargeable and removable ($\sim$3 hours autonomy) \\ \midrule
\tableheadline{Light barrier} & \acs{IR} LED (emitter,left side) with {IR} transistor (receiver,right side)\\ \midrule
\tableheadline{LEDs} & 3 RGB LEDs (left side, right side, top) \\ \midrule
\tableheadline{Connectivity} & 802.15.4 XBee DigiMesh (Wireless) \\ \midrule
\tableheadline{Programming languages} & Processing, C, C++   \\ \midrule
\bottomrule
\end{tabularx}
\end{scriptsize}\caption[Overview of the technical specifications of the \emph{TAM} device]{Overview of the technical specifications of the \emph{TAM} device}  
\label{tab:tamspec}
\end{table}



%------------------------------------------------

\subsection{\acl{ARGoS}}
\label{subsec:ARGoS}
\graffito{\ac{ARGoS} 2.0 development has been discontinued, the new version of the simulator, still in beta testing phase, is available at \url{https://github.com/ilpincy/argos3}}
\ac{ARGoS}\footnote{\url{http://iridia.ulb.ac.be/argos/home.php}} is a multi-robot simulator, written in C++, and released under GPL-3 license.

It has been developed by \cite{pinciroli2012argos} in the framework of the EU-Funded project Swarmanoid \footnote{\url{http://www.swarmanoid.org}} which is also the official simulator of the EU-Funded projects ASCENS\footnote{\url{http://ascens-ist.eu}}, H2SWARM\footnote{\url{
http://www.esf.org/activities/eurocores/running-programmes/eurobiosas/collaborative-research-projectscrps/h2swarm.html}},
and E-SWARM\footnote{\url{
http://www.e-swarm.org/}}.

Since the Swarmanoid project dealt with a swarm of heterogeneous robots, two main issues had to be addressed by the simulator: \emph{flexibility} and \emph{efficiency}.

In order to be \emph{flexible} the simulator should allow the user to implement and integrate new features (e.g. sensors or robot models).
In \acs{ARGoS}, flexibility is achieved through a modular architecture on every level.
Every simulated entity, from the sensors to the physics engine, is implemented as a plugin, which can be easily modified or extended by the end-user.
A similar architecture supports the existence of different versions of the same components (e.g. actuators/sensors with/without noise models, fine vs coarse grained physical simulations) making the simulation accuracy highly tunable.

Moreover, the plugin nature of the components (Figure \ref{fig:ARGoSArchitecture}) allow the user to load only the required ones, making the simulation more efficient.
Efficiency is also achieved through the support for the simultaneous simulation of different physical engines, each one of them assigned to non overlapping regions of the simulation space, resulting in an improved allocation of computational resources.
Furthermore, the multi-threaded architecture of the simulator can profit of the presence of multiple core \acs{CPU}s.


\begin{figure}[H]
\centering
\includegraphics[width=\linewidth,keepaspectratio]{Gfx/ARGoSArchitecture}
\caption[Architecture of \acs{ARGoS}]{Architecture of \acs{ARGoS}. The white boxes correspond to user-definable plug-ins. 

From \protect\cite{pinciroli2012argos} in Swarm Intelligence, Volume 6, Issue 4, December 2012. Reprinted with permission from Springer Science and Business Media. All rights reserved.
}
\label{fig:ARGoSArchitecture}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[width=\linewidth,keepaspectratio]{Gfx/ARGoSScreenshot}
\caption[Screenshot of the ARGoS simulator for the scenario B environment configuration]{Screenshot of the ARGoS simulator for the scenario B environment configuration.}
\label{fig:ARGoS}
\end{figure}


In addition to the aforementioned properties, we decided to use \emph{ARGoS} since it offers full support for the \emph{e-puck} robot (all the sensors/actuators are simulated).

In order to launch a working simulation, \acs{ARGoS} requires two components to be provided: the \emph{controllers} and the \emph{configuration file}.

The \emph{controllers} are plugins which make use of all the other components provided by the simulator to implement the individual behavior of an entity (\emph{TAM} and \emph{e-puck}, in our case).
They consist of C++ source files (.cpp), with the respective headers (.h), which must be compiled prior to be dynamically loaded at runtime.
The control interface to write robot controllers in \emph{ARGoS} is common to both simulated and real robots.
This means that the transition between simulated and real robots is seamless, requiring only a recompilation for a different target architecture (except for the \emph{TAM}). 

The \emph{configuration file} is an \acs{XML} file which describes the structure of the simulated environment (physics engines, placement of mobile and static objects, placement of the cameras) and which is used to map each simulated entity with the corresponding controller, giving also the possibility to pass parameters to it.

Another important functionality offered by \acs{ARGoS} is the possibility to create \emph{loop functions}.
The simulation loop in \emph{ARGoS} involves three phases: \emph{sense and control}, \emph{act}, \emph{ update}.
In the first phase, the values of the \emph{sensors} are read and passed to the code of the user defined \emph{controller}, which is then executed, modifying the state of the actuators.
Then, in the \emph{act} phase, the actions stored in the actuators are executed.
Lastly, in the \emph{update phase}, the physics engine updates the state of the entities under its control.

\emph{Loop functions} are user-defined functions hooks that are placed in precise points in the simulation loop (i.e. at initialization time, before and after the execution of the \emph{update} phase).
By means of this tool, the user is able to query the physics engine and to modify its state at run time.
This allows us to collect data at each simulation step for further processing and visualization.





